Sajad Sohrabi Hesan; Freydoon Rahbarnia; Mostafa Tavakolli
Abstract
Given any graph G, its square graph G^2 has the same vertex set as G, with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. The Cartesian product of graphs G and H is denoted by G□ H. One of the most studied NP-hard problems is the graph coloring ...
Read More
Given any graph G, its square graph G^2 has the same vertex set as G, with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. The Cartesian product of graphs G and H is denoted by G□ H. One of the most studied NP-hard problems is the graph coloring problem. A method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by researchers for many years. In this paper, we use the graph product approach to this problem. In fact, we prove that X((D(m',n')□D(m,n))^2)<= 10 for m,n => 3, where D(m, n) is the graph obtained by joining a vertex of the cycle C_m to a vertex of degree one of the paths P_n and X(G) is the chromatic number of the graph $G$.
